Recall that Newton’s Method is given by the iteration x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. This method is guaranteed to converge under the following conditions:
Theorem.
Suppose f: [a,b] \to \mathbb R is twice continuously differentiable with f(\xi) = 0 and f'(\xi) \not= 0 for some \xi \in [a,b]. Further suppose that
\begin{align}
\left|\frac{f''(x)}{f'(y)}\right| \leq A
\end{align}
for all x,y \in [a,b]. Then, the Newton iteration x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} converges at least quadratically to \xi for all x_1 \in [a,b] such that |x_1 - \xi| \leq A^{-1}.
Each of the following parts is worth 50 pts.
15.1 A. Repeated Roots
Suppose that f(\xi) = f'(\xi) = 0 (so that the above theorem is not applicable) and that there exists 0 < m < M < 2m such that m < |f''(x)| < M for all x \in [\xi-\delta, \xi+\delta].
✍ Show that there exists \eta_n, \theta_n between x_n and \xi such that the sequence generated by Newton’s method (x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}) satisfies
Since f'(\xi) = 0 and by the mean value theorem, there exists \theta_n between x_n and \xi such that f'(x_n) = f'(x_n) - f'(\xi) = f''(\theta_n) ( x_n - \xi ) and so
Since L := \frac12 \frac{M}{m} < \frac12\frac{2m}{m} = 1, we find that x_{n+1} \in [\xi-\delta, \xi+\delta]. Therefore, for x_1 \in [\xi- \delta, \xi +\delta], the sequence (x_n) is contained in [\xi- \delta, \xi +\delta] and
Therefore, the convergence is linear (with asymptotic error constant \frac12).
💻 Verify this numerically by finding the zero of f(x) = (x-1)^2 and estimating the asymptotic error constant \mu.
Answer.
We have f(1) = f'(1) = 0 and f''(x) = 2 which satisfies 0 < \frac32 < f''(x) < \frac52 for all x\in \mathbb R. In particular, f satisfies the conditions stated above. That is, we expect the Newton iteration to converge linearly with asymptotic error constant \frac12 which is what we observe numerically:
f = x -> (x-1)^2df = x ->2*(x-1)x =Newton( f, df, 2. ) orderOfConvergence( x, 1., α=1 )
If \xi is a repeated root of f, then we have seen that the Newton iteration can converge slower than quadratically (we saw linear convergence in parts 2 and 3). However, \xi is also a root of g but now it is a simple root (g'(\xi) \not= 0). Therefore, in practice, if one can show that g''(x) is bounded near \xi, then Newton’s iteration starting near \xi will converge quadratically.
15.2 C. Newton’s Method Examples
💻 Run Newton’s Method on the following functions (it may help to plot the functions in order to choose a good initial point x_1)
💻 If the iteration converges, what is the (numerically calculated) order of convergence?
✍ In each case, explain why your observations do not contradict the Theorem stated above and do not contradict your observations made in part A.
Answer.
First, we note that g(0) = h(0) = j(0) = 0 and, because f(2) < 0 < f(3) (and f is continuous), f has a root \xi \in [2,3]:
f = x -> x^3-2*x^2-5df = x ->3*x^2-4*x d2f = x ->6*x -4g = x ->exp(x) - x -1dg = x ->exp(x) -1h = x -> x/(1+ x^2)dh = x -> (1- x^2)/(1+ x^2)^2d3h = x ->-6*( x^4-6*x^2+1 )/(x^2+1)^4# I write the function like this so that we choose the real cube root# i.e. -1, exp( ± π/3 ) are all cube roots of -1 j = x ->sign(x) *abs(x)^(1/3)dj = x -> (1/3) * (x^2)^(-1/3)plot( [f, g, h, j] , -1, 3, ylims=(-1,2), label=[L"f" L"g" L"h" L"j"], lw =2)hline!( [0], linestyle=:dash, primary =false )
f:
The Newton iteration starting at x_1 = 2 applied to f converges to \xi \approx 2.691.... The order of convergence appears to be quadratic (see next cell).
This behaviour is supported by the theorem from lectures (and also on the top of this notebook): f is twice continuously differentiable with f'(x) = 3x^2 - 4x and f''(x) = 6x - 4. Therefore, for x, y \in [2,3], we have
We have g(x) = e^x - x - 1 and so g'(x) = e^x - 1 and g(0) = g'(0) = 0. Moreover, g''(x) = e^x and so we have 0 < \frac34 < g''(x) < \frac54 < 2\frac34 = \frac32 for all x \in ( \log \frac34, \log \frac54 ). As a result, there exists a closed interval about 0 for which we may apply the result presented in section A of this assignment. That is, Newton’s iteration converges linearly with asymptotic error constant \frac12.
h:
The Newton iteration starting at x_1 = 0.5 applied to h converges to 0. (We choose x_1 \not= 1 so that h'(x_1) \not= 0 and x_2 is well defined). The order of convergence appears to be cubic (order 3):
xh =Newton( h, dh, .5)orderOfConvergence( xh, 0., α=3)println( "theoretical value of μ = ", (1/3) *abs(d3h(0)/dh(0)) )
and so h(0) = 0 and h'(0) \not= 0. We have h''(0) = 0 and so for x,y close enough to 0, we have the bound |\frac{h''(x)}{h'(y)}| \leq A for some A. As a result, the theorem from lectures tells us that the convergence is at least quadratic. In this case however, we see that h''(0) = 0 and this leads to faster convergence: we briefly mentioned in lectures that in this case the convergence is at least cubic with asyptotic error constant \mu = \frac13 \left|\frac{h'''(\xi)}{h'(\xi)}\right|.
j:
The Newton iteration starting at x_1 = 1 applied to j does not converge:
┌ Warning: max interations |f| = 7.999999999999996
└ @ Main In[36]:49
We have that j'(x) = \frac13 x^{-\frac23} is unbounded near the root 0 and so we cannot apply any of the results from lectures and we cannot apply the results from section A. In fact, we have
and so the sequence diverges with |x_{n+1}| = 2|x_n| = \cdots = 2^{n} |x_1|. Therefore, the Newton iteration diverges for all x_1 \not= 0 (and is also not defined for x_1 = 0).
